import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
        static class ListNode {
            int val;
            ListNode next;
            ListNode (){};
            ListNode (int val) {
                this.val = val;
            }
            ListNode (int val,ListNode next) {
                this.val = val;
                this.next = next;
            }
        }
        public static int getDecimalValue(ListNode head) {
            ListNode cur = head;
            String str = "0";
            while(cur != null) {
                str += cur.val;
                cur = cur.next;
            }
            int a = Integer.parseInt(str,2);
            return a;
        }
    public static void main1(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(1);
        node1.next = node2;
        node2.next = null;
        ListNode head = node1;
        getDecimalValue(head);
        int a = getDecimalValue(head);
        System.out.println(a);
    }

    public static int[] main1(ListNode head) {
        ListNode node0 = new ListNode(5);
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(5);
        ListNode node5 = new ListNode(1);
        ListNode node6 = new ListNode(2);
        head = node0;
        node0.next  = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = null;
        int minDistance = Integer.MAX_VALUE,maxDistance=0;
        int firstIndex = -1;
        int prevIndex = -1;
        int curIndex = -1;
        int index = 1;
        ListNode cur = head.next;
        while(cur.next != null) {
            if((cur.val > head.val && cur.val >cur.next.val )||
                    (cur.val < head.val && cur.val < cur.next.val)) {
                if(firstIndex < 0) {
                    firstIndex = index;
                }
                prevIndex = curIndex;
                curIndex = index;
                if(prevIndex >= 0) {
                    minDistance = Math.min(minDistance,curIndex - prevIndex);
                    maxDistance = Math.max(maxDistance,curIndex - firstIndex);
                }
            }
            head = head.next;
            cur = cur.next;
            index++;
        }
        if(minDistance <= maxDistance) {
            return new int[]{minDistance,maxDistance};
        }else   {
            return new int[]{-1,-1};
        }
    }

    public static ListNode main2(ListNode head   ) {
        ListNode pre = head;
        for(ListNode cur = head.next;cur.next!=null;cur = cur.next) {
            if(cur.val != 0) {
                pre.val += cur.val;
            } else {
                pre = pre.next;
                pre.val = 0;
            }
        }
        pre.next = null;
        return head;
    }
    public static ListNode  main1(ListNode head1,int a,int b,ListNode head2) {
            ListNode cur1= head1;
            ListNode A = null,B = null;
            while(--a > 0 && --b > 0){
                head1 = head1.next;
            }
            A = head1;
            while(b-- > 0) {
                head1 = head1.next;
            }
            B = head1.next;
            A.next = head2;
            while(head2.next != null) {
                head2 = head2.next;
            }
            head2.next = B;
            return cur1;
        }

    public static ListNode removeNodes(ListNode head   ) {
        if(head.next == null) {
            return head;
        }
        ListNode node = removeNodes(head.next);
        if(node.val > head.val) {
            return node;
        }
        head.next = node;
        return head;
    }

    public static void main5(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

    public static ListNode main6(ListNode head) {
        ListNode pre = new ListNode(0,head);
        ListNode cur = pre;
        while(cur.next != null && cur.next.next !=null) {
            int val = cur.next.val;
            if(val == cur.next.next.val) {
                while(cur.next != null && cur.next.val == val) {
                    cur.next = cur.next.next;
                }
            }else{
                cur = cur.next;
            }
        }
        return pre.next;
    }

    public static ListNode main7(ListNode head) {
        ListNode cur = head;
        if(cur == null ) {
            return head;
        }
        while(cur.next != null) {
            if(cur.val == cur.next.val) {
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }

        }
        return head;
    }

    public static ListNode main8(int[] nums,ListNode head) {
        Set<Integer> set = new HashSet<>(nums.length);
        for(int x:nums) {
            set.add(x);
        }
        ListNode node1 = new ListNode(0,head);
        ListNode cur = node1;
        while(cur.next != null) {
            if(set.contains(cur.next.val)) {
                cur.next = cur.next.next;
            }else {
                cur = cur.next;
            }
        }
        return node1.next;
    }

    public static ListNode main9(ListNode head,int val) {
        if(head == null) {
            return head;
        }
        ListNode cur = head.next;
        ListNode pre = head;
        while(cur != null) {
            if(cur.val == val) {
                pre.next = cur.next;
                cur = cur.next;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        if(head.val == val) {
            head = head.next;
        }
        return head;
    }

    public static int main0(int[] nums,ListNode head) {
        int[] index = new int[10001];
        for(int num : nums){
            index[num] = 1;
        }
        int result = 0,pre = 0;
        while(head != null ) {
            if (pre == 0 && index[head.val] == 1) {
                result++;
            }
            pre = index[head.val];
            head = head.next;
        }
        return result;
    }

    public static ListNode[] main(ListNode head,int k) {
        int n = 0;
        ListNode cur = head;
        while(cur != null) {
            n++;
            cur = cur.next;
        }
        int mod = n % k;
        int size = n / k;
        ListNode[] res = new ListNode[k];
        cur = head;
        for(int i = 0;i < k && cur != null;i++) {
            res[i] = cur;
            int cursize = size + (mod-- > 0 ? 1 : 0);
            for(int j = 0;j < cursize - 1;j ++) {
                cur = cur.next;
            }
            ListNode next = cur.next;
            cur.next = null;
            cur = next;
        }
        return res;
    }

}




